package sort.memory;

/**
 * 希尔排序
 * @author：涂有
 * @date 2017年11月26日 下午4:24:40
 */
public class ShellSort {
	
	public static void sort(int[] a){
		sort(a, a.length >> 1);
	}

	private static void sort(int[] a, int gap){
		if(gap < 1) return;
		for(int i = 0; i < gap; i++){
			insertSort(a, i, gap);
		}
		sort(a, gap >> 1);
	}
	
	/**
	 * 对数组中指定间隔的元素做插入排序
	 * @author：涂有
	 * @date 2017年11月26日 下午5:44:20
	 * @param a
	 * @param start 开始位置
	 * @param gap 元素之间间隔距离
	 */
	private static void insertSort(int a[], int start, int gap){
		for(int i = start; i < a.length - gap; i += gap){
			int min = i + gap;
			for(int j = i; j >= start; j -= gap){
				if(a[min] < a[j]){
					SortUtil.swap(a, j, min);
					min = j;
				}
			}
		}
	}
}
